Search Results

Documents authored by Jin, Yi

Found 2 Possible Name Variants:

Jin, Yi

Document
DOI: 10.4230/DagSemProc.05321.5
Actions and Belief Revision : A Computational Approach

Authors: Yi Jin and Michael Thielscher

Published in: Dagstuhl Seminar Proceedings, Volume 5321, Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics (2005)

Abstract
The classic AGM theory studies mathematically idealized models of belief revision in two aspects: the properties (i.e., the AGM postulates) a rational revision operator should satisfy; and how to mathematically construct concrete revision operators. In scenarios where new information arrives in sequence, rational revision operators should also respect postulates for iterated revision (e.g., the DP postulates). When applications are concerned, the idealization of the AGM theory has to be lifted, in particular, beliefs of an agent should be represented by a finite belief base. In this talk, we present a computational base revision operator, which satisfies the AGM postulates and some nice postulates for iterated revision. We will also give a formal assessment of the base revision operator in terms of its computational complexity and degree of syntax irrelevance.
Cite as

Yi Jin and Michael Thielscher. Actions and Belief Revision : A Computational Approach. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{jin_et_al:DagSemProc.05321.5,
  author =	{Jin, Yi and Thielscher, Michael},
  title =	{{Actions and Belief Revision : A Computational Approach}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5321},
  editor =	{James Delgrande and Jerome Lang and Hans Rott and Jean-Marc Tallon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05321.5},
  URN =		{urn:nbn:de:0030-drops-3599},
  doi =		{10.4230/DagSemProc.05321.5},
  annote =	{Keywords: Iterated Belief Revision, Belief Base Revision, Computational Complexity}
}

Jin, Yifei

Document
DOI: 10.4230/LIPIcs.SoCG.2018.49
Odd Yao-Yao Graphs are Not Spanners

Authors: Yifei Jin, Jian Li, and Wei Zhan

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
It is a long standing open problem whether Yao-Yao graphs YY_{k} are all spanners [Li et al. 2002]. Bauer and Damian [Bauer and Damian, 2012] showed that all YY_{6k} for k >= 6 are spanners. Li and Zhan [Li and Zhan, 2016] generalized their result and proved that all even Yao-Yao graphs YY_{2k} are spanners (for k >= 42). However, their technique cannot be extended to odd Yao-Yao graphs, and whether they are spanners are still elusive. In this paper, we show that, surprisingly, for any integer k >= 1, there exist odd Yao-Yao graph YY_{2k+1} instances, which are not spanners.
Cite as

Yifei Jin, Jian Li, and Wei Zhan. Odd Yao-Yao Graphs are Not Spanners. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jin_et_al:LIPIcs.SoCG.2018.49,
  author =	{Jin, Yifei and Li, Jian and Zhan, Wei},
  title =	{{Odd Yao-Yao Graphs are Not Spanners}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.49},
  URN =		{urn:nbn:de:0030-drops-87621},
  doi =		{10.4230/LIPIcs.SoCG.2018.49},
  annote =	{Keywords: Odd Yao-Yao Graph, Spanner, Counterexample}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.25
SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms

Authors: Lingxiao Huang, Yifei Jin, and Jian Li

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
We study two important SVM variants: hard-margin SVM (for linearly separable cases) and nu-SVM (for linearly non-separable cases). We propose new algorithms from the perspective of saddle point optimization. Our algorithms achieve (1-epsilon)-approximations with running time O~(nd+n sqrt{d / epsilon}) for both variants, where n is the number of points and d is the dimensionality. To the best of our knowledge, the current best algorithm for nu-SVM is based on quadratic programming approach which requires Omega(n^2 d) time in worst case [Joachims, 1998; Platt, 1999]. In the paper, we provide the first nearly linear time algorithm for nu-SVM. The current best algorithm for hard margin SVM achieved by Gilbert algorithm [Gärtner and Jaggi, 2009] requires O(nd / epsilon) time. Our algorithm improves the running time by a factor of sqrt{d}/sqrt{epsilon}. Moreover, our algorithms can be implemented in the distributed settings naturally. We prove that our algorithms require O~(k(d +sqrt{d/epsilon})) communication cost, where k is the number of clients, which almost matches the theoretical lower bound. Numerical experiments support our theory and show that our algorithms converge faster on high dimensional, large and dense data sets, as compared to previous methods.
Cite as

Lingxiao Huang, Yifei Jin, and Jian Li. SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.SWAT.2018.25,
  author =	{Huang, Lingxiao and Jin, Yifei and Li, Jian},
  title =	{{SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.25},
  URN =		{urn:nbn:de:0030-drops-88515},
  doi =		{10.4230/LIPIcs.SWAT.2018.25},
  annote =	{Keywords: nu-SVM, hard-margin SVM, saddle point optimization, distributed algorithm}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact